In existing computation devices, a dedicated electronic circuit may be used to multiply two binary numbers. In the multiplication electronic circuit, the digital multipliers may be implemented in a variety of techniques; most of them involve computing a set of partial products, and then summing the partial products together. This process is similar to the method taught to primary schoolchildren for conducting long multiplication on decimal numbers.
In each step of the multiplication process of decimal numbers, the partial product represents the multiplication result between a multiplicand and a different digit of a multiplier. As known, the right most digit represents the number of “ones”) (100) of a number, the next digit represents the number of “tens” (101) and so forth with the rest of the digits representing hundreds (102), thousands (103) etc. Therefore, the first partial product represent the number of “ones” in the final result, the second partial product represents the number of “tens” in the final result and so forth with the rest of the partial products. As each partial product represents a different power of 10, each new partial product is shifted one location to the left with respect to the previous partial product.
A similar procedure is employed for multiplying multi-bit binary numbers as illustrated in FIG. 1 to which reference is now made. Multi-bit multiplication 100 is an example in which A is the multiplicand and B is the multiplier in a multiplication operation between two 5-bit binary numbers. In each step, multiplicand A is multiplied by one bit of multiplier B, starting with the left most bit of B, and the result of each step is a partial product (PP). The value of the kth partial product is computed by multiplying bit k of multiplier B by A and by (2k). The first partial product represents the value of bit 0 of multiplier B multiplied by A and by)(20). The next PP represents the value of bit 1 of multiplier B multiplied by A and by (21). The next PP represents the value of bit 2 of multiplier B multiplied by A and by 22 and so on. The multiplication by 2k is equivalent to shifting k times to the left.
The first partial product PP-1 is the result of multiplying bit 0 of B and is not shifted. The second partial product PP-2 is the result of multiplying bit 1 of B therefore, PP-2 is shifted one location to the left with respect to PP-1. An empty space 110 is created by the left shift in the Least Significant Bit (LSB) position of PP-2, and an empty space 111 may be perceived in the Most Significant Bit (MSB) position of PP-1. A similar procedure is done with respect to the third, fourth and fifth digits of B, providing PP-3, PP-4 and PP-5, each shifted one location to the left with respect to the previous partial product, i.e. each multiplied by the relevant power of 2.
It may be appreciated that the value of empty spaces 110 and 111 is 0, as is the value of all other empty spaces of all partial products created during multiplication in both the LSB and MSB positions.
It may be appreciated that the value of a bit of multiplier B may be either 0 or 1; therefore, the value of each partial product may be either 0 or A: If the value of a bit from B is 0, then the value of the resultant partial product may be 0, and if the value of a bit from B is 1, then the value of the resultant partial product is A.
After all bits of B have been processed, a sum of all partial products is calculated. The number of partial products is the number of bits in B, and the sum may be calculated by repeatedly using a standard multi-bit adder with carry propagation (not shown in the figure) between any two partial products to provide the final result. It may be noted that the “empty” locations in the rightmost bits of a partial product actually have the value “0” such that, for example, the value of PP-3 represented by the number 10011 shifted two positions to the left is actually 1001100.
It may be appreciated that the sum of all partial products is done by performing an add operation between each pair of partial products, one bit at a time to enable the carry to propagate from the LSB to the MSB. This may provide a complexity of O(n) for each sum operation. The number of partial products is n; therefore, the complexity of the complete multiplication operation may be O(n2), i.e. the number of partial products—n (which is the number of bits of the multiplier which defines the number of add operations) multiplied by the number of bits of each partial product—n (the number of bits of the multiplicand participating in each add operation).
The number of bits resulting from a multiplication operation between two n-bit numbers may be 2n−1 or 2n.
It may be appreciated that the concurrent multi-bit adder defined in U.S. patent application Ser. No. 15/690,301, now issued as U.S. Pat. No. 10,402,165, entitled “CONCURRENT MULTI-BIT ADDER”, assigned to the common assignee of the present invention and incorporated here by reference, may improve the complexity of the add operation by operating concurrently on groups of bits, but may not provide concurrent operations on all bits and may provide a complexity proportional to the number if groups of bits which is >1.
It may be appreciated that the number of bits of the multiplier does not have to be identical to the number of bits of the multiplicand. When the sizes are n and m, the complexity of the multiplication may be O(mn).